1. Field of the Invention
The present invention relates to encoding, detection, and decoding of data in communication systems, and, more particularly, to a product code with interleaving for error detection and correction by a receiver.
2. Description of the Related Art
Many digital transmission systems commonly employ techniques for detection of digital data represented by a sequence of symbols. The symbol bits are transferred as a signal through a transmission (i.e., communication) channel in which noise is typically added to the transmitted signal. For example, magnetic recording systems first encode data into symbol bits that are recorded on a magnetic medium. Writing data to, storing data in, and reading data from the magnetic medium may be considered to take place via a transmission channel that has an associated frequency response. Similarly, wired, optical, wireless, and cellular communication systems also transfer encoded data through a channel that is then detected and decoded by a receiver. The signal may be read from the channel as a sampled signal (i.e., a sequence of sample values) representing the transmitted encoded data. For processing convenience, the encoding and decoding process is applied to blocks of data, each block representing a portion of the original data sequence.
Encoding data with two-dimensional or higher block codes and subsequent decoding of the encoded data are employed in many systems due to the relatively high coding gain and simple structure of the decoder. Product codes may be employed for encoding of data in which two or more simple codes (known as component codes) are combined to create more powerful encoding schemes. The dimension of the code may be related to the number of component codes.
For example, a product code may employ a parity-bit check code that, for the two-dimensional case, encodes N information bits as two-dimensional data words (e.g., n1 words having n2 information bits, or n2 words having n1 information bits). Each data word represents a vector in a corresponding dimension, and n1 and n2 are integers greater than 0. The product code encoding of the data (i.e., the N information bits) are ordered in a rectangular matrix u, and the encoding may be a row vector (e.g., n1 information bits) by column vector (e.g., n2 information bits) combination to form the rectangular matrix u. The combination may be GF(2) addition, multiplication, or linear operation of the binary values. For example, a sequence of N information bits (e.g., a block of data) may be formed as an (n1xc3x97n2) matrix of information bits, with N=n1n2. The product code encoding of the data also includes row- and column-wise parity bits pr and pc, respectively, as error detection and correction information. Horizontal rows are formed from n2 code words of an (n1, k1) block code Cr having rate R1=(n1/k1) (here, k1 is the total length of a row, and the length of the parity bit information for each row is k1xe2x88x92n1). Vertical columns are formed from n1 code words of an (n2, k2) block code Cc having rate R2=(n2/k2) (here, k2 is the total length of a column, and the length of the parity bit information for each column is k2xe2x88x92n2).
The block of data encoded with the product code is typically transmitted as a serial block of encoded data. Product codes typically exhibit optimum performance with respect to coding gain when correcting for single one-bit errors when single-bit parity check codes are employed per dimension. Only single, one-bit errors may be detected and corrected because of parity-check cancellation arising from an even number of errors occurring in a row or in a column and parity-check positional ambiguities associated with multiple one-bit errors. For an example of this positional ambiguity in a square, product code matrix with single bit parity check codes, let the first element of the first row be in error, and the second element of the second row be in error (errors along the forward diagonal). Both the first and second row-wise and first and second column-wise parity bits will indicate an error, but they will also indicate an error if the second element of the first row and the first element of the second row is in error (errors in the reverse diagonal). Detection and correction of higher numbers of errors, especially higher numbers of consecutive errors, may add excessive overhead in terms of error detection information (e.g., parity bits), reducing overall system throughput. Errors in data at the receiver may be caused by incorrect decisions of the detection and/or decoding process because of signal degradation. Signal degradation occurs from added random and/or burst noise as the signal passes through the communication channel.
A characteristic of some communication channels is the addition of xe2x80x9cburstyxe2x80x9d noise. Such noise may corrupt a transmitted signal for a period of time equivalent to the period of several transmitted symbols (either data or encoded data). Bursty noise may cause burst errors in the received data. To minimize the effect of burst errors, many communication systems include an interleaver in the transmitter and a corresponding de-interleaver in the receiver. Interleaving is a mappingƒ(*) that generally comprises receiving a block of data having BLK values (i.e., BLK is the block length and BLK is an integer greater than one), and rearranging the order of the BLK values in the block. Interleaving may also be employed, for example, to remove non-random sequences of values in a data stream. By interleaving the symbols in a block of data prior to transmission through the channel, the de-interleaving process distributes the burst errors throughout the de-interleaved block.
The term xe2x80x9coutput channel samplexe2x80x9d refers to a sample of encoded data from the transmission channel generated through the sampling process of the receiver. A receiver typically includes a detector to detect the sequence of symbol bits representing the encoded data from the output channel samples. A decoder receives the detected symbol sequence from the detector and decodes the sequence of symbol bits to reconstruct the data. The decoder may be a simple decoder reversing the encoding process, or an iterative decoder that repetitively decodes the data until a predetermined decoding metric, such as a maximum bit-error rate (BER) threshold, is satisfied. The detector and the decoder may each typically employ a partial response, maximum-likelihood (PRML) algorithm (e.g., Viterbi algorithm (VA)), a maximum a posteriori (MAP) algorithm, or a soft-output Viterbi algorithm (SOVA).
These algorithms used by detectors and/or decoders typically determine a maximum-likelihood path through a trellis of states. The path represents a sequence of decisions for symbols corresponding to the received output channel samples. However, in situations where the received signal has low signal-to-noise ratio (SNR), the algorithm may determine an incorrect path through the trellis, thereby generating an incorrect sequence of decisions for a corresponding sequence of output channel samples. Such sequence of errors is commonly termed an xe2x80x9cerror eventxe2x80x9d of the detection algorithm. For some error events, the decision for the sequence of received bits may generate a long sequence of errors, which are thus inserted into the detected encoded data prior to decoding. Consequently, the detection algorithms used in a particular implementation are optimized based on channel memory, SNR, and impulse response, and indirectly with respect to dominant error events.
The present invention relates to encoding a block of data with a product code and interleaving of the values of the encoded block to enhance error detection and correction of the product code. The error correction capability of the product code detects and corrects M-bit errors in an encoded block, M a positive integer. The encoded block is interleaved by applying a mapping to the encoded block based on an error constraint ER, ER a positive integer that is greater than or equal to M. Errors may be added to the interleaved and encoded data after transmission through a communication channel by, for example, burst noise or from an error event in the detection process. The mapping of the interleaving process is selected to distribute a sequence of up to ER errors throughout a de-interleaved block of encoded data as one or more M-bit errors, and position the one or more M-bit errors uniquely along a path through the B-dimensional matrix after de-interleaving. For the example of a two-dimensional product code detecting and correcting single-bit error, the values of the up to ER errors are distributed so no two of the ER error values are in the same row or column after the interleaved, encoded data block received from a channel is de-interleaved. In addition, the values of the up to ER errors are distributed so the one or more M-bit errors are uniquely positioned along, e.g., the forward or reverse diagonals of the matrix to reduce or prevent positional ambiguities associated with the parity check code bits. Consequently, combining the product code and interleaving process may allow for detection and correction of a greater number of bit errors in received data than when only the error correction capability of the product code is employed. Detection and correction of bit errors is enhanced since the decoding process has a priori information referring to the position of distributed M-bit errors, if present, in the encoded block.
In accordance with one exemplary embodiment of the present invention, a block of data is encoded to enable error detection and correction after passing as a signal through a communications channel. The block of data is encoded with a B-dimensional product code to generate an encoded block, B a positive integer greater than 1, wherein the product code encodes the block of data with error correction and detection information having an M-bit error correction capability, M a positive integer. The elements of the encoded block are interleaved according to an interleaving depth. The interleaving depth is selected based on an error constraint ER and the M-bit error correction capability to provide a predefined distance between, and unique position of, adjacent elements of up to ER errors in the interleaved encoded block when it is de-interleaved, ER a positive integer greater than or equal to M.
In accordance with another exemplary embodiment of the present invention, an interleaved, encoded block of data is detected and decoded after passing as a signal through a communications channel. The block of data is encoded with a B-dimensional product code to generate the encoded block, B a positive integer greater than 1, and the block of data is encoded with the B-dimensional product code that includes error correction and detection information having an M-bit error correction capability, M a positive integer. The set of values are interleaved in accordance with an interleaving depth, the interleaving depth selected based on an error constraint ER and the M-bit error correction capability to provide a predefined distance between, and unique position of, adjacent elements of up to ER errors in the interleaved encoded block when it is de-interleaved, ER a positive integer greater than or equal to M. The interleaved, encoded block of data is detected from the communications channel and either 1) de-interleaved after detection or 2) decoded in accordance with the product code and de-interleaved after decoding to generate output values. The error correction and detection information is employed to correct, in accordance with the M-bit error correction capability and the unique position of the adjacent elements after de-interleaving, each M-bit error in the output values after de-interleaving.